The technique of genetic optimization is well known for enabling computerised generation of an optimum solution to a problem by selection from a pool of candidates in a manner analogous to natural genetic selection. A model creates outputs in response to inputs defining potential solutions, which outputs are evaluated against it for fitness until an optimum solution is found or a cut off point is reached. The structure of the candidate solutions is defined in the model as a string of parameters representing different properties of the solution. Each specific solution is an instance of the general structure in which specific values are ascribed to the parameters. The process of optimization involves generation of new candidate solutions from the original pool of candidates followed by subsequent iterative generation of further solutions from the modified pool. Poor solutions, as determined by the fitness evaluation are rejected and better solutions selected for the pool.
Thus the candidate solutions may be thought of as analogous to individual or multiple chromosomes and the parameters to genes of living organisms. In order to generate further candidate solutions, crossing techniques analogous to cross breeding are employed whereby portions of two solutions (parents) are combined to form a new solution (child), still meeting the overall structure. This operation is known as a crossover operation. Several types of crossover are possible depending on rules defining exactly how portions of candidate solutions may be combined. A simple example would be where the first half portion of one candidate solution was combined with the second half portion of another candidate solution. Clearly many other ways of combining and rearranging the parameter values of two solutions are possible.
Also known is a mutation operation whereby a defined proportion of the candidate solutions have individual or multiple parameter values changed. This could be done, for example, by means of a random number generator. This is analogous to natural mutation of the genes of living organisms.
Such a known system is illustrated in the flow diagram of FIG. 1 in which candidates from an initial pool 1 are selected for mutation or crossover in decision box 2. In the case of mutation, a single parent, already judged to be promising, is selected at step 3 and its parameters mutated in step 4. In the case of crossover, two promising parents are selected at step 5 and their parameters crossed in step 6. The resulting new candidates are evaluated in step 7 and, if adjudged to be improvements, are fed back to the pool 1, replacing the inferior candidates, and are available for further crossing or mutation.
Clearly, such genetic optimization techniques are extremely demanding of computing time and resources, depending on the number of candidates to be considered and mutated or crossed and on the number of iterations employed in arriving at, if not the optimum, at least an acceptable solution.
Various approaches have been tried in the prior art in attempting to minimize the time and resources needed to reach an optimum acceptable solution. These can involve altering the rules for crossover or mutation, for evaluating fitness for purpose and limiting the number of iterations carried out.
One example of a technique for increasing the efficiency of a genetic algorithm applied to computer programming is described in US Patent Application Publication 2003/004904 A1 entitled “Multi-Module Genetic Programming with Multiple Genetic Data Representations”This employs multiple genetic data component representations for different modules of the solution. Each module is characterised by a “model” and realised by referring to one or more of the genetic data components. Evolution of a solution by using crossover operations is made more efficient by matching the genetic data component representations before crossover so that like component representations are crossed rather than ones of different type.
Another example of an attempt to improve efficiency is described in US Patent Application Publication 2004/0081977 A1 entitled “Genetic Algorithm Convergence Accelerating Apparatus, System and Method for the same”This uses a pipelining technique to speed up the processing of crossover operations, a technique referred to as “hypergeneration crossover”It is claimed that convergence is faster and the solution is closer to the optimal than with conventional techniques.
Neither of these documents addresses the special situation of optimization of a solution where a model defines the structure of the solution or goal to be achieved as a group of objects (A,B,C) in combination, the objects consisting of defined parameters and being identically structured. Such a group may also be thought of as a defined set of submodels. Conventionally, two candidate solutions each including an identically structured group, say, A1, B1 and C1 and A2, B2 and C2 might be crossed in sequence or by name, thus: A1 with A2, B1 with B2 and C1 with C2. This would produce a relatively random group of children not necessarily converging towards an optimum solution and, in general, it has been found that crossover does not work well in this scenario.